F - LCS
LCS(Longest Common Subsequence)…最長共通部分列を求める問題です。これでも、DPが使えます。
考え方
dp[i文字目までのs][j文字目までのt]で、最長の長さを値として持っておけば良いそうです。
え？文字列出力するんじゃ…、と思ったんですが、この問題は「復元」がキーポイントになってくるそうです。
貰うDPの方が考えやすいかも。
入出力例1
table:example1
"" "a" "ax" "axy" "axyb"
"" 0 0 0 0 0
"a" 0 1 1 1 1
"ab" 0 1 1 1 2
"aby" 0 1 1 2 2
"abyx" 0 1 2 2 2
"abyxb" 0 1 2 2 3
完成形を表にするとこうなります。Zの字を描くように埋めていくことにします。0-indexedです。0行目から始まります。
初期化
まずは初期化です。""の行や列は全て0にしていいので、0で埋めておきます。
table:example0
"" "a" "ax" "axy" "axyb"
"" 0 0 0 0 0
"a" 0
"ab" 0
"aby" 0
"abyx" 0
"abyxb" 0
まずは左上から1行目を左から順に埋めていきます。最後の文字が一致した時は、LCSの長さは左上の数字+1になります。
table:example0
"" "a" "ax" "axy" "axyb"
"" 0 0 0 0 0
"a" 0 1 1 1 1
"ab" 0
"aby" 0
"abyx" 0
"abyxb" 0
1行目から埋めてみました。1,1,1,1って感じです。"a"の最後の文字「a」と"a"の最後の文字「a」が一致していたので、クロスしているところ、つまり1行1列目の値は、そこの左上(0行0列)の値「0」に1を足したもの、1になります。
”a”と"a"の最後の文字が同じだったので、"a"と"a"のLCSの長さは、""と""のLCSの長さ+1 = 1になる
そんな感じで2行目も埋めていきます。
table:example0
"" "a" "ax" "axy" "axyb"
"" 0 0 0 0 0
"a" 0 1 1 1 1
"ab" 0 1 1 1 2
"aby" 0
"abyx" 0
"abyxb" 0
埋まりました。途中で2になっています。"axyb"の最後の文字「b」と"ab"の最後の文字「b」が一致していたので、そのマスの値は左上+1になりました。はい。
”axyb”と"ab"の最後の文字が同じだったので、"axyb"と"ab"のLCSの長さは、"axy"と"a"のLCSの長さ+1 = 1になる
復元
こんな感じで埋めていって、最後に右下の数字を出力…では終わらないです。復元大切です。
書くの疲れた（おい）